#include <iostream>
using namespace std;
#define maxn 2001

int t,n,m,k;
int C[maxn][maxn], S[maxn][maxn];

void buildC(){
	C[0][0]=1;
	for(int i=1; i<maxn; i++){
		for(int j=0; j<=i; j++){
			C[i][j] = C[i-1][j] + C[i-1][j-1];
			C[i][j] %= k;
		}
	}
	for(int i=2; i<maxn; i++){
		for(int j=1; j<maxn; j++){
			S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1];
			if(C[i][j]==0 && j<=i) S[i][j]++;
		}
	}
}

int main(){
	cin>>t>>k;
	buildC();
	for(int tt=0; tt<t; tt++){
		cin>>n>>m;
		cout<<S[n][m]<<endl;
	}
	return 0;
}